加载可能比较慢,可以尝试点击脚注标,会弹出相关内容

王道操作系统视频 提取码: axin

考纲内容

(一)进程与线程

• 进程与线程的基本概念：进程/线程的状态与转换
• 线程的实现：内核支持的线程,线程库支持的线程
• 进程与线程的组织与控制
• 进程间通信：共享内存,消息传递,管道

(二)CPU调度与上下文切换

• 调度的基本概念：调度的目标
• 调度的实现：调度器/调度程序(scheduler),调度的时机与调度方式(抢占式/非抢占式),闲逛进程,内核级线程与用户级线程调度
• 典型调度算法：先来先服务调度算法;短作业(短进程、短线程)优先调度算法,时间片轮转调度算法,优先级调度算法,高响应比优先调度算法,多级队列调度算法,多级反馈队列调度算法
• 上下文及其切换机制

(三)同步与互斥

• 同步与互斥的基本概念
• 基本的实现方法：软件方法;硬件方法
• 锁：信号量;条件变量
• 经典同步问题：生产者-消费者问题,读者-写着问题;哲学家就餐问题

(四)死锁

• 死锁的基本概念;死锁预防
• 死锁的避免;死锁检测和解除

【复习提示】

进程管理是操作系统的核心,也是每年必考的重点。其中,进程的概念、进程调度、信号量机制实现同步和互斥、进程死锁等更是重中之重,必须深入掌握。需要注意的是,除选择题外,本章还容易出综合题,其中信号量机制实现同步和互斥、进程调度算法和死锁等都可能命制综合题,如利用信号量进行进程同步就在往年统考频繁出现。

2.1 进程与线程

思考问题

1. 为什么要引入进程？
2. 什么是进程？进程由什么组成？
3. 进程是如何解决问题的？

2.1.1 进程的概念和特征

1.进程的概念

在多道程序环境下,允许多个程序并发执行,此时它们将试去封闭性及不可再现性的特征。为此引入进程(Process)的概念,以便更好地描述和抗旨程序的并发执行,实现操作系统的并发性和共享性(最基本的两个特征)。

为了使参与并发执行的每个程序(含数据)都能独立地运行,必须为之配置一个专门的数据结构,称为进程控制块(Process Control Block,PCB)。系统利用PCB来描述进程的基本情况和运行状态,进而控制和管理进程。相应地,由程序段、相关数据段和PCB三个部分构成了进程实体(又称进程映像)。所谓创建进程,实质上是创建进程实体中的PCB;而撤销进程,实质上是撤销进程的PCB。值得注意的是,进程映像是静态的,进程则是动态的。

[!NOTE] 注意：PCB是进程存在的唯一标志！

引入进程实体概念后,我们可以把传统操作系统中的进程定义为：“进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。”

这里说的系统资源指处理机、存储器和其他设备服务于某个进程的“时间”,例如把处理机资源理解为处理机的时间片才准确。因为进程是这些资源分配和调度的独立单位,即“时间片”分配到独立单位,这就决定了进程一定是一个动态的、过程性的概念。

2.进程的特征(不必记忆只求理解)

• （1）^动态性
• （2）^并发性
• （3）^独立性
• （4）^异步性

2.1.2 进程的状态与转换

通常进程有以下5种状态,前3种是进程的基本状态。

• （1）^运行态
• （2）^就绪态
• （3）^阻塞态
• （4）^创建态
• （5）^终止态

图2.1说明了5种进程状态的转换,而3种基本状态之间的转换如下：

• 阻塞态 → 运行态：处于就绪态的进程被调度后,获得处理机资源(分派处理机时间片),于是进程由就绪态转换为运行态。
• 运行态 → 就绪态：处于运行态的进程在时间片用完后,不得不让出处理机,从而进程由运行态转换为就绪态。此外,在可剥夺的操作系统中,当有更高优先级的进程就绪时,调度程序将正在执行的进程转换为就绪态,让更高优先级的进程执行。
• 运行态 → 阻塞态：进程请求某一资源(如外设)的使用和分配或等待某一事件的发生(如I/O操作的完成)时,它就从运行态转换为阻塞态。进程以系统调用的形式请求操作系统提供服务,这是一种特殊的、由运行用户态程序调用操作系统内核过程的形式。
• 阻塞态 → 就绪态：进程等待的事件到来时,如I/O操作结束或中断结束时,中断处理程序必须把相应进程的状态由阻塞态转换为就绪态。

需要注意：一个进程从运行态变成阻塞态是主动的行为,而从阻塞态变成就绪态是被动的行为,需要其他相关进程的协助。

2.1.3 进程的组成

进程是一个独立的运行单位,也是操作系统进行资源分配和调度的基本单位。它由以下三部分组成,其中最核心的是进程控制块(PCB)。

1.进程控制块

进程创建时,操作系统为它新建一个PCB,该结构之后常驻内存,任意时刻都可以存取,并在进程结束时删除。PCB是进程实体的一部分,是进程存在的唯一标志。
进程执行时,系统通过其PCB了解进程的现行状态信息,以便操作系统对其进行控制和管理;进程结束时,系统收回其PCB,该进程随之消亡。
当操作系统欲调度某进程运行时,要从该进程的PCB中查出其现行状态及优先级;在调度到某进程后,要根据其PCB中所保存的处理机状态信息,设置该进程恢复运行的现场,并根据其PCB中的程序和数据的内存始址,找到其程序和数据;进程在运行过程中,当需要和与之合作的进程实现同步、通信或访问文件时,也需要访问PCB;当进程由于某种原因而暂停运行时,又需将其断点的处理机环境保存在PCB中。可见,在进程的整个生命期中,系统总是通过PCB对进程进行控制的,亦即系统唯有通过进程的PCB才能感知到该进程的存在。

表2.1是一个PCB的实例。PCB主要包括进程描述信息、进程控制和管理信息、资源分配清单和处理机相关信息等。各部分的主要说明如下：

表2.1及相关内容

1)进程描述信息。进程标识符：标志各个进程,每个进程都有一个唯一的标识号。用户标识符：进程归属的用户,用户标识符主要为共享和保护服务。
2)进程控制和管理信息。进程当前状态：描述进程的状态信息,作为处理机分配调度的依据。进程优先级：描述进程抢占处理机的优先级,优先级高的进程可优先获得处理机。
3)资源分配清单,用于说明有关内存地址空间或虚拟地址空间的状况,所打开文件的列表和所使用的输入输出设备信息。
4)处理机相关信息,也称处理机的上下文,主要指处理机中各寄存器的值。当进程处于执行态时,处理机的许多信息都在寄存器中。当进程被切换时,处理机状态信息都必须保存在相应的PCB中,以便在该进程重新执行时,能从断点继续执行。

---

在一个系统中,通常存在着许多进程的PCB,有的处于就绪态,有的处于阻塞态,而且阻塞的原因各不相同。为了方便进程的调度和管理,需要将各进程的PCB用适当的方法组织起来。目前,常用的组织方式有^链接方式和^索引方式两种。

2.程序段

• ^程序段

3.数据段

• ^数据段

2.1.4 进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理,它具有创建新进程、撤销已有进程、实现进程状态转换等功能。在操作系统中,一般把进程控制用的程序段称为原语,原语的特点是执行期间不允许中断,它是一个不可分割的基本单位。

1. ^{进程的创建}

   • 操作系统创建一个新进程的过程(创建原语):
     • 1)为新进程分配一个唯一的进程标识号,并申请一个空白PCB (PCB是有限的)。若PCB申 请失败,则创建失败。
     • 2)为进程分配其运行所需的资源,如内存、文件、I/O 设备和CPU 时间等 (在PCB 中体 现)。这些资源或从操作系统获得,或仅从其父进程获得。如果资源不足(如内存),则 并不是创建失败,而是处于创建态,等待内存资源。
     • 3)初始化 PCB, 主要包括初始化标志信息、初始化处理机状态信息和初始化处理机控制信 息,以及设置进程的优先级等。
     • 4)若进程就绪队列能够接纳新进程,则将新进程插入就绪队列,等待被调度运行。

2. ^{进程的终止}

   • 操作系统终止进程的过程如下(终止原语)：
     • 1)根据被终止进程的标识符,检索出该进程的PCB,从中读出该进程的状态。
     • 2)若被终止进程处于运行状态,立即终止该进程的执行,将处理机资源分配给其他进程。
     • 3)若该进程还有子孙进程,则应将其所有子孙进程终止。
     • 4)将该进程所拥有的全部资源,或归还给其父进程,或归还给操作系统,灯考研
     • 5)将该PCB从所在队列(链表)中删除。

3. ^{进程的阻塞和唤醒}

   • 阻塞原语(Block)
     • 1)找到将要被阻塞进程的标识号对应的PCB.
     • 2)若该进程为运行态,则保护其现场,将其状态转为阻塞态,停止运行。
     • 3)把该PCB插入相应事件的等待队列,将处理机资源调度给其他就绪进程。
   • 唤醒原语(Wakeup)
     • 1)在该事件的等待队列中找到相应进程的PCB.
     • 2)将其从等待队列中移出,并置其状态为就绪态。
     • 3)把该PCB插入就绪队列,等待调度程序调度。
   • ^{注意Block&Wakeup}

2.1.5进程的通信

进程通信是指进程之间的信息交换。PV操作是低级通信方式,高级通信方式是指以较高的效率传输大量数据的通信方式。

• 共享存储
• 消息传递
  • 直接通信方式
  • 间接通信方式
• 管道通信

2.1.6 线程和多线程模型

1. ^{线程的基本概念}
2. 线程与进程的比较
   • 1)调度。在传统的操作系统中,拥有资源和独立调度的基本单位都是进程,每次调度都要进行上下文切换,开销较大。在引入线程的操作系统中,线程是独立调度的基本单位,而线程切换的代价远低于进程。在同一进程中,线程的切换不会引起进程切换。但从一个进程中的线程切换到另一个进程中的线程时,会引起进程切换。
   • 2)并发性。在引入线程的操作系统中,不仅进程之间可以并发执行,而且一个进程中的多个线程之间亦可并发执行,甚至不同进程中的线程也能并发执行,从而使操作系统具有更好的并发性,提高了系统资源的利用率和系统的吞吐量。
   • 3)拥有资源。进程是系统中拥有资源的基本单位,而线程不拥有系统资源(仅有一点必不可少、能保证独立运行的资源),但线程可以访问其隶属进程的系统资源,这主要表现在属于同一进程的所有线程都具有相同的地址空间。要知道,若线程也是拥有资源的单位,则切换线程就需要较大的时空开销,线程这个概念的提出就没有意义。
   • 4)独立性。每个进程都拥有独立的地址空间和资源,除了共享全局变量,不允许其他进程访问。某个进程中的线程对其他进程不可见。同一进程中的不同线程是为了提高并发性及进行相互之间的合作而创建的,它们共享进程的地址空间和资源。
   • 5)系统开销。在创建或撤销进程时,系统都要为之分配或回收进程控制块PCB及其他资源,如内存空间、I/O设备等。操作系统为此所付出的开销,明显大于创建或撤销线程时的开销。类似地,在进程切换时涉及进程上下文的切换,而线程切换时只需保存和设置少量寄存器内容,开销很小。此外,由于同一进程内的多个线程共享进程的地址空间,因此这些线程之间的同步与通信非常容易实现,甚至无须操作系统的干预。
   • 6)支持多处理器系统。对于传统单线程进程,不管有多少个CPU,进程只能运行在一个CPU上。对于多线程进程,可将进程中的多个线程分配到多个CPU上执行。
3. 线程的属性
   • 1)线程是一个轻型实体,它不拥有系统资源,但每个线程都应有一个唯一的标识符和一个线程控制块,线程控制块记录线程执行的寄存器和栈等现场状态。
   • 2)不同的线程可以执行相同的程序,即同一个服务程序被不同的用户调用时,操作系统将它们创建成不同的线程。
   • 3)同一进程中的各个线程共享该进程所拥有的资源。
   • 4)线程是CPU的独立调度单位,多个线程是可以并发执行的。在单CPU的计算机系统中,各线程可交替地占用CPU;在多CPU的计算机系统中,各线程可同时占用不同的CPU,若各个CPU同时为一个进程内的各线程服务,则可缩短进程的处理时间。
   • 5)一个线程被创建后,便开始了它的生命周期,直至终止。线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态变化。
4. 线程的状态与转换
   • 执行态：线程已获得CPU而正在运行。
   • 就绪态：线程已具备各种执行条件,只需再获得CPU便可立即执行。
   • 阻塞态：线程在执行中因某事件受阻而处于暂停状态。
5. 线程的组织与控制
   • 线程控制块
   • 线程的创建
   • 线程的终止

1. 线程的实现方式
   • 用户级线程(User-Level Thread,ULT)
     • 优点：
       • ①线程切换不需要转换到内核空间,节省了模式切换的开销。
       • ②调度算法可以是进程专用的,不同的进程可根据自身的需要,对自己的线程选择不同的调度算法
       • ③用户级线程的实现与操作系统平台无关,对线程管理的代码是属于用户程序的一部分。
     • 缺点：
       • ①系统调用的阻塞问题,当线程执行一个系统调用时,不仅该线程被阻塞,而且进程内的所有线程都被阻塞。
       • ②不能发挥多CPU的优势,内核每次分配给一个进程的仅有一个CPU,因此进程中仅有一个线程能执行。
   • 内核级线程(Kernel-Level Thread,KLT)。内核级线程又称内核支持的线程。
     • 优点：
       • ①能发挥多CPU的优势,内核能同时调度同一进程中的多个线程并行执行。
       • ②如果进程中的一个线程被阻塞,内核可以调度该进程中的其他线程占用CPU,也可运行其他进程中的线程。
       • ③内核支持线程具有很小的数据结构和堆栈,线程切换比较快、开销小。
       • ④内核本身也可采用多线程技术,可以提高系统的执行速度和效率。
     • 缺点：同一进程中的线程切换,需要从用户态转到核心态进行,系统开销较大。这是因为用户进程的线程在用户态运行,而线程调度和管理是在内核实现的。
   • 组合方式 (有些系统使用组合方式的多线程实现。在组合实现方式中,内核支持多个内核级线程的建立、调度和管理,同时允许用户程序建立、调度和管理用户级线程。一些内核级线程对应多个用户级线程,这是用户级线程通过时分多路复用内核级线程实现的。同一进程中的多个线程可以同时在多CPU上并行执行,且在阻塞一个线程时不需要将整个进程阻塞,所以组合方式能结合KLT和 ULT的优点,并且克服各自的不足。图2.5(©)展示了这种组合实现方式。)

线程库(thread library)是为程序员提供创建和管理线程的API。实现线程库主要的方法有如下两种：

• ①在用户空间中提供一个没有内核支持的库。这种库的所有代码和数据结构都位于用户空间中。这意味着,调用库内的一个函数只导致用户空间中的一个本地函数的调用。

• ②实现由操作系统直接支持的内核级的一个库。对于这种情况,库内的代码和数据结构位于内核空间。调用库中的一个API函数通常会导致对内核的系统调用。

• 多线程模型

• 1)多对一模型。将多个用户级线程映射到一个内核级线程,如图2.6(a)所示。每个进程只被分配一个内核级线程,线程的调度和管理在用户空间完成。仅当用户线程需要访问内核时,才将其映射到一个内核级线程上,但每次只允许一个线程进行映射。
  • 优点：线程管理是在用户空间进行的,无须切换到核心态,因而效率比较高。
  • 缺点：如果一个线程在访问内核时发生阻塞,则整个进程都会被阻塞：在任何时刻,只有一个线程能够访问内核,多个线程不能同时在多个CPU上运行。
• 2)一对一模型。将每个用户级线程映射到一个内核级线程,如图2.6(b)所示。每个进程有与用户级线程数量相同的内核级线程,线程切换由内核完成,需要切换到核心态。
  • 优点：当一个线程被阻塞后,允许调度另一个线程运行,所以并发能力较强。
  • 缺点：每创建一个用户线程,相应地就需要创建一个内核线程,开销较大。
• 3)多对多模型。将n个用户级线程映射到m个内核级线程上,要求n≥m,如图2.6(c)所示。特点：既克服了多对一模型并发度不高的缺点,又克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。此外,还拥有上述两种模型各自的优点。

2.1.7 本节小结

1. 为什么要引入进程？ 在多道程序设计的背景下,进程之间需要共享系统资源,因此会导致各程序在执行过程中出现相互制约的关系,程序的执行会表现出间断性等特征。这些特征都是在程序的执行过程中发生的,是动态的过程,而传统的程序本身是一组指令的集合,是静态的概念,无法描述程序在内存中的执行情况,即无法从程序的字面上看出它何时执行、何时停顿,也无法看出它与其他执行程序的关系,因此,程序这个静态概念已不能如实反映程序并发执行过程的特征。为了深刻描述程序动态执行过程的性质乃至更好地支持和管理多道程序的并发执行,便引入了进程的概念。
2. 什么是进程？进程由什么组成？ 进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源,是一个动态的概念,是一个活动的实体。它不只是程序的代码本身,还包括当前的活动,通过程序计数器的值和处理寄存器的内容来表示。一个进程实体由程序段、相关数据段和PCB三部分构成,其中PCB是标志一个进程存在的唯一标识,程序段是进程运行的程序的代码,数据段则存储程序运行过程中相关的一些数据。
3. 进程是如何解决问题的？ 进程将能够识别程序运行状态的一些变量存放在PCB中,通过这些变量系统能够更好地了解进程的状况,并在适当时机进行进程的切换,以避免一些资源的浪费,甚至划分为更小的调度单位一一线程来提高系统的并发度。

2.1.8 本节习题精选

一、单项选择题

二、综合应用题

04.某分时系统中的进程可能出现如下图所示的状态变化,请回答下列问题：
1)根据图示,该系统应采用什么进程调度策略？
2)将图中每个状态变化的可能原因填写在下表中。

根据题意,首先由图进行分析,进程由运行态可以直接回到就绪队列的末尾,而且就绪队列中是先来先服务。那么,什么情况才能发生这样的变化呢？只有采用单一时间片轮转的调度系统,分配的时间片用完后,才会发生上述情况。因此,该系统一定采用时间片轮转调度算法,采用时间片轮转算法的操作系统一般均为交互式操作系统。由图可知,进程被阻塞时,可以进入不同的阻塞队列,等待打印机输出结果和等待磁盘读取文件。所以,它是一个多阻塞队列的时间片轮转法的调度系统。
具体解答如下。
1)根据题意,该系统采用的是时间片轮转法调度进程策略。

---

2)可能的变化见下表。

2.2 CPU调度

2.2.1 调度的概念

1. ^{调度的基本概念}

1. 调度的层次

一个作业从提交开始直到完成,往往要经历以下三级调度,如图2.7所示。

• (1)^{高级调度(作业调度)}
• (2)^{中级调度(内存调度)}

• (3)^{低级调度(进程调度)}

• 三级调度的联系

作业调度从外存的后备队列中选择一批作业进入内存,为它们建立进程,这些进程被送入就绪队列,进程调度从就绪队列中选出一个进程,并将其状态改为运行态,将CPU分配给它。中级调度是为了提高内存的利用率,系统将那些暂时不能运行的进程挂起来。

• 1)作业调度为进程活动做准备,进程调度使进程正常活动起来。
• 2)中级调度将暂时不能运行的进程挂起,中级调度处于作业调度和进程调度之间。
• 3)作业调度次数少,中级调度次数略多,进程调度频率最高。
• 4)进程调度是最基本的,不可或缺。

2.2.2 调度的实现

1. 调度程序(调度器)

用于调度和分派CPU的组件称为调度程序,它通常由三部分组成,如图2.8所示。

• 1)^排队器
• 2)^分派器

• 3)^{上下文切换器}

• 调度的时机、切换与过程

调度程序是操作系统内核程序。请求调度的事件发生后,才可能运行调度程序,调度了新的就绪进程后,才会进行进程切换。理论上这三件事情应该顺序执行,但在实际的操作系统内核程序运行中,若某时刻发生了引起进程调度的因素,则不一定能马上进行调度与切换。

现代操作系统中,应该进行进程调度与切换的情况如下：

• 1)创建新进程后,由于父进程和子进程都处于就绪态,因此需要决定是运行父进程还是运行子进程,调度程序可以合法地决定其中一个进程先运行。
• 2)进程正常结束后或者异常终止后,必须从就绪队列中选择某个进程运行。若没有就绪进程,则通常运行一个系统提供的闲逛进程。
• 3)当进程因I/O请求、信号量操作或其他原因而被阻塞时,必须调度其他进程运行。
• 4)当I/O设备完成后,发出I/O中断,原先等待I/O的进程从阻塞态变为就绪态,此时需要决定是让新的就绪进程投入运行,还是让中断发生时运行的进程继续执行。

1. 进程调度的方式 所谓进程调度方式,是指当某个进程正在CPU上执行时,若有某个更为重要或紧迫的进程需要处理,即有优先权更高的进程进入就绪队列,此时应如何分配CPU。

2. 1)非抢占调度方式,又称非剥夺方式。

是指当一个进程正在CPU上执行时,即使有某个更为重要或紧迫的进程进入就绪队列,仍然让正在执行的进程继续执行,直到该进程运行完成(如正常结束、异常终止)或发生某种事件(如等待I/O操作、在进程通信或同步中执行了Block原语)而进入阻塞态时,才将CPU分配给其他进程。

[!NOTE] 非抢占调度方式的优点是实现简单、系统开销小,适用于早期的批处理系统,但它不能用于分时系统和大多数的实时系统。

• 2)抢占调度方式,又称剥夺方式。

是指当一个进程正在CPU上执行时,若有某个更为重要或紧迫的进程需要使用CPU,则允许调度程序根据某种原则去暂停正在执行的进程,将CPU分配给这个更为重要或紧迫的进程。

[!NOTE] 抢占调度方式对提高系统吞吐率和响应效率都有明显的好处。但“抢占”不是一种任意性行为,必须遵循一定的原则,主要有优先权、短进程优先和时间片原则等。

1. ^闲逛进程

2. 两种线程的调度

3. 1)^{用户级线程调度}

4. 2)^{内核级线程调度}

2.2.3 调度的目标

不同的调度算法具有不同的特性,在选择调度算法时,必须考虑算法的特性。为了比较CPU调度算法的性能,人们提出了很多评价标准,下面介绍其中主要的几种：

• 1)^CPU利用率。CPU利用率的计算方法如下：

[!NOTE] 计算作业完成时间时,要注意CPU与设备、设备与设备之间是可以并行的。

• 2)^{系统吞吐量}。
• 3)^周转时间。周转时间的计算方法如下：

• 4)^等待时间。
• 5)^响应时间。

2.2.4 进程切换

• (1)^{上下文切换}
  • 1)挂起一个进程,将CPU上下文保存到PCB,包括程序计数器和其他寄存器。
  • 2)将进程的PCB移入相应的队列,如就绪、在某事件阻塞等队列。
  • 3)选择另一个进程执行,并更新其PCB。
  • 4)恢复新进程的CPU上下文。
  • 5)跳转到新进程PCB中的程序计数器所指向的位置执行。
• (2)^{上下文切换的消耗}
• (3)^{上下文切换与模式切换}

[!NOTE] 调度和切换的区别：调度是指决定资源分配给哪个进程的行为,是一种决策行为;切换是指实际分配的行为,是执行行为。一般来说,先有资源的调度,然后才有进程的切换。

2.2.5 典型的调度算法

1. ^{先来先服务(FCFS)调度算法}
   • FCFS调度算法的特点是算法简单,但效率低;对长作业比较有利,但对短作业不利(相对SJF和高响应比);有利于CPU繁忙型作业,而不利于I/O繁忙型作业。
2. ^{短作业优先(JSF)调度算法} (最短剩余时间优先调度算法)
   • 1)该算法对长作业不利,SJF调度算法中长作业的周转时间会增加。更严重的是,若有一长作业进入系统的后备队列,由于调度程序总是优先调度那些(即使是后进来的)短作业,将导致长作业长期不被调度,产生“饥饿”现象(注意区分“死锁”,后者是系统环形等待,前者是调度策略问题)。
   • 2)该算法完全未考虑作业的紧迫程度,因而不能保证紧迫性作业会被及时处理。
   • 3)由于作业的长短是根据用户所提供的估计执行时间而定的,而用户又可能会有意或无意地缩短其作业的估计运行时间,致使该算法不一定能真正做到短作业优先调度。

[!NOTE] 短作业(SJF)调度算法的平均等待时间、平均周转时间是最优的

1. 高响应比优先调度算法

根据公式可知：

• ①作业的等待时间相同时,要求服务时间越短,响应比越高,有利于短作业,因而类似于SJF。
• ②要求服务时间相同时,作业的响应比由其等待时间决定,等待时间越长,其响应比越高,因而类似于FCFS。

• ③对于长作业,作业的响应比可以随等待时间的增加而提高,当其等待时间足够长时,也可获得CPU,克服了“饥饿”现象。

• ^{优先级调度算法}

• 根据新的更高优先级进程能否抢占正在执行的进程,可将该调度算法分为如下两种：

  • 1)^{静态优先级}。
  • 2)^{动态优先级}。一般来说,进程优先级的设置可以参照以下原则：
    • 1)^{系统进程>用户进程}。
    • 2)^{交互型进程>非交互型进程} (或前台进程>后台进程)。
    • 3)^{I/O型进程>计算型进程}。

1. ^{时间片轮转(RR)调度算法}

时间片轮转(RR)调度算法主要适用于分时系统。

在RR调度算法中,时间片的大小对系统性能的影响很大。若时间片足够大,以至于所有进程都能在一个时间片内执行完毕,则时间片轮转调度算法就退化为先来先服务调度算法。若时间片很小,则CPU将在进程间过于频繁地切换,使CPU的开销增大,而真正用于运行用户进程的时间将减少。因此,时间片的大小应选择适当,时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。

1. ^{多级队列调度算法}

1. 多级反馈队列调度算法(融合了前几种算法的优点)

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展,如图2.9所示。通过动态调整进程优先级和时间片大小,多级反馈队列调度算法可以兼顾多方面的系统目标。例如,为提高系统吞吐量和缩短平均周转时间而照顾短进程：为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程;同时,也不必事先估计进程的执行时间。

• 多级反馈队列调度算法的实现思想如下：

  • 1)设置多个就绪队列,并为每个队列赋予不同的优先级。第1级队列的优先级最高,第2级队列的优先级次之,其余队列的优先级逐个降低。
  • 2)赋予各个队列的进程运行时间片的大小各不相同。在优先级越高的队列中,每个进程的时间片就越小。例如,第i+1级队列的时间片要比第i级队列的时间片长1倍。
  • 3)每个队列都采用FCFS算法。新进程进入内存后,首先将它放入第1级队列的末尾,按 FCFS原则等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可撤离系统。若它在一个时间片结束时尚未完成,调度程序将其转入第2级队列的末尾等待调度;若它在第2级队列中运行一个时间片后仍未完成,再将它放入第3级队列,以此类推。当进程最后被降到第n级队列后,在第n级队列中便采用时间片轮转方式运行。
  • 4)按队列优先级调度。仅当第1级队列为空时,才调度第2级队列中的进程运行：仅当第1~ i-1级队列均为空时,才会调度第i级队列中的进程运行。若CPU正在执行第i级队列中的某个进程时,又有新进程进入任何一个优先级较高的队列,此时须立即将正在运行的进程放回到第i级队列的末尾,而将CPU分配给新到的高优先级进程。

• 多级反馈队列的优势有以下几点：

  • 1)终端型作业用户：短作业优先。
  • 2)短批处理作业用户：周转时间较短。
  • 3)长批处理作业用户：经过前面几个队列得到部分执行,不会长期得不到处理。

调度算法总结

2.2.6 本节小结

1. 为什么要进行CPU调度？

若没有CPU调度,则意味着要等到当前运行的进程执行完毕后,下一个进程才能执行,而实际情况中,进程时常需要等待一些外部设备的输入,而外部设备的速度与CPU相比是非常缓慢的,若让CPU总是等待外部设备,则对CPU的资源是极大的浪费。而引进CPU调度后,可在运行进程等待外部设备时,将CPU调度给其他进程,从而提高CPU的利用率。用一句简单的话说,就是为了合理地处理计算机的软/硬件资源。

1. 调度算法有哪几种？结合第1章学习的分时操作系统和实时操作系统,思考有没有哪种调度算法比较适合这两种操作系统。

本节介绍的调度算法有先来先服务调度、短作业优先调度、优先级调度、高响应比优先调度、时间片轮转调度、多级队列调度、多级反馈队列调度7种。
先来先服务算法和短作业优先算法无法保证及时地接收和处理问题,因此无法保证在规定的时间间隔内响应每个用户的需求,也同样无法达到实时操作系统的及时性需求。优先级调度算法按照任务的优先级进行调度,对于更紧急的任务给予更高的优先级,适合实时操作系统。
高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法都能保证每个任务在一定时间内分配到时间片,并轮流占用CPU,适合分时操作系统。

2.2.7 本节习题精选

一、单项选择题

[!NOTE] 第3题答案原C,但解析来看是B,但阿鑫认为是B(可能打印错误)。具体正确答案自行分析。

20.一个作业8:00到达系统，估计运行时间为1h。若10:00开始执行该作业，其响应比是()。

A.2 B.1 C.3 D.0.5

C

---

25.

A.8.62;6.34 B.8.62;6.8 C.10.62;6.34 D.10.62;6.8

D

---

27.

A.25h B.26h C.27h D.28h

C

---

37.【2012统考真题】一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5s到达，它的计算和I/O操作顺序如下：
P1:计算60ms,I/O 80ms,计算20ms
P2:计算120ms,I/O 40ms,计算40ms
若不考虑调度和切换时间，则完成两个作业需要的时间最少是()。

A.240ms B.260ms C.340ms D.360ms

B

---

39.

A.P1>P2>P3 B.P3>P2>P1 C.P2>P1=P3 D.P1>P2=P3

B

---

为了合理地设置进程优先级，应综合考虑进程的CPU时间和I/O时间。对于优先级调度算法，一般来说，I/O型作业的优先权高于计算型作业的优先权，这是由于/O操作需要及时完成，它没有办法长时间地保存所要输入/输出的数据，所以考虑到系统资源利用率，要选择/O繁忙型作业有更高的优先级。

41.【2016统考真题】某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms,3ms和4ms,且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是()。

A.15ms B.17ms C.22ms D.27ms

B

---

42.

A.J2,J3 B.J1,J4 C.J2,J4 D.J1,J3

D

---

注意，系统是在t=2时开始作业调度的，此时J4还没有到达。FCFS调度算法的特点是作业来得越早，优先级就越高，因此选择J1。SJF调度算法的特点是作业运行时间越短，优先级就越高，因此选择J3

44.【2018统考真题】某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1μS。在T时刻就绪队列中有3个进程P1、P2和P3,其在就绪队列中的等待时间、需要的CPU时间和优先权如下表所示。

A.54μs B.73μs C.74μs D.75μs

D

---

由优先权可知，进程的执行顺序为P2→P3→P1。P2的周转时间为1+15+24=40μS;P3的周转时间为18+1+24+1+36=80μs:P1的周转时间为30+1+24+1+36+1+12=105μs:平均周转时间为(40+80+105)/3=225/3=75us,因此选择选项D。

45.【2019统考真题】系统采用二级反馈队列调度算法进行进程调度。就绪队列Q1采用时间片轮转调度算法，时间片为10s;就绪队列Q2采用短进程优先调度算法;系统优先调度Q1队列中的进程,当Q1为空时系统才会调度Q2中的进程;新创建的进程首先进入Q1;Q1中的进程执行一个时间片后,若未结束,则转入Q2。若当前Q,Q2为空，系统依次创建进程P1,P2后即开始进程调度，P1,P2,需要的CPU时间分别为30ms和20ms,则进程P1,P2,在系统中的平均等待时间为()。

A.25ms B.20ms C.15ms D.10ms

C

---

49.

A.4 B.5 C.6 D.7

C

---

需要注意的是，在0时刻，P0获得CPU也是一次进程调度，故0时刻调度进程Po获得CPU;10ms时P2进入就绪队列,调度P2抢占获得CPU;15ms时P3进入就绪队列，调度P3抢占获得CPU;25ms时P3执行完毕，调度P2获得CPU;40ms时P2执行完毕，调度P0获得CPU:130ms时P0执行完毕，调度P1获得CPU;190ms时P1执行完毕，结束;总共调度6次。

50. 若系统采用基于优先权的抢占式CPU调度算法，从Os时刻开始进行调度，则P1、P2和P3的平均周转时间为()。

A.60ms B.61ms C.70ms D.71ms

B

---

二、综合应用题

02.

[!NOTE] SJF的平均周转时间肯定是最短的，计算完毕后可以利用这个性质进行检验

2.3 同步与互斥

2.3.1 同步与互斥的基本概念

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。

1. ^临界资源

对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可将临界资源的访问过程分成4个部分：

• 1)进入区。为了进入临界区使用临界资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
• 2)临界区。进程中访问临界资源的那段代码，又称临界段。
• 3)退出区。将正在访问临界区的标志清除。
• 4)剩余区。代码中的其余部分。

while(true){
  entry section;    //进入区
  critical section; //临界区
  exit section;     //退出区
  remainder section;//剩余区
}

1. ^同步

2. ^互斥

为禁止两个进程同时进入临界区，同步机制应遵循以下准则：

• 1)空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
• 2)忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
• 3)有限等待。对请求访问的进程，应保证能在有限时间内进入临界区，防止进程无限等待。
• 4)让权等待(原则上应该遵循，但非必须)。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

2.3.2 实现临界区互斥的基本方法

1. ^{软件实现方法}

(1)算法一：单标志法

该算法设置一个公用整型变量turn,指示允许进入临界区的进程编号，当trun=0时，表示允许P0。进入临界区;当turn=1时，表示允许P1,进入临界区。进程退出临界区时将临界区的使用权赋给另一个进程，当Pi,退出临界区时，将turn置为j(i=0、j=1或i=1、j=0)。

该算法可以实现每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，若某个进程不再进入临界区，则另一个进程也将无法进入临界区(违背“空闲让进”准则)。这样很容易造成资源利用不充分。若P0顺利进入临界区并从临界区离开，则此时临界区是空闲的，但P1并没有进入临界区的打算，而turn=1一直成立，则P0就无法再次进入临界区。

(2)算法二：双标志先检查法

该算法设置一个布尔型数组fag[2],用来标记各个进程想进入临界区的意愿，flag[i]=true表示Pi,想要进入临界区(i=0或1)。Pi进入临界区前，先检查对方是否想进入临界区，若想，则等待;否则，将flag[i]置为true后，再进入临界区;当Pi退出临界区时，将flag[i]置为false。

优点：不用交替进入，可连续使用。缺点：P0和P1可能同时进入临界区。按序列①②③④执行时，即检查对方标志后和设置自己的标志前可能发生进程切换，结果双方都检查通过，会同时进入临界区(违背“忙则等待”准则)。原因在于检查和设置操作不是一气呵成的。

(3)算法三：双标志后检查法

算法二先检查对方的标志，再设置自己的标志，但这两个操作又无法一气呵成，于是使得两个进程同时进入临界区的问题。因此，想到先设置后检查法，以避免上述问题。算法三先设置自己的标志，再检查对方的标志，若对方的标志为true,则等待;否则，进入临界区。

按序列①②③④执行时，即两个进程依次设置自己的标志，并依次检查对方的标志，发现对方也想进入临界区，双方都争着进入临界区，结果谁也进不了(违背“空闲让进”准则)，于是因各个进程都长期无法访问临界区而导致“饥饿”现象(违背“有限等待”准则)。

(4)算法四：Peterson算法

Peterson算法结合了算法一和算法三的思想，利用flag解决互斥访问问题，而利用turn解决“饥饿”问题。若双方都争着进入临界区，则可让进程将进入临界区的机会谦让给对方。也就是说，在每个进程进入临界区之前，先设置自己的flag标志，再设置允许进入turn标志;之后，再同时检测对方的flag和turn标志，以保证双方同时要求进入临界区时，只允许一个进程进入。

为进入临界区，Pi先将flag置为true,并将turn置为j，表示优先让对方Pj进临界区(i=0、 j=1或i=1、j=0)。若双方试图同时进入，则turn几乎同时被置为i和j,但只有一个赋值语句的结果会保持，另一个也会执行，但会被立即重写。变量turn的最终值决定了哪个进程被允许先进入临界区，若turn的值为i,则Pi进入临界区。当Pi退出临界区时，将flag[i]置为false,以允许Pj进入临界区，则Pj在Pj退出临界区后很快就进入临界区。若Pi不想进入临界区，即flag[i]=false(Pj不会陷入while循环)，则Pj就可进入临界区。
由此可见，Peterson算法很好地遵循了“空闲让进”“忙则等待”“有限等待”三个准则，但依然未遵循“让权等待”准则。相比于前三种算法，该算法是最好的，但依然不够好。

1. 硬件实现方法

• (1)^{中断屏蔽方法}
• (2)^{硬件指令方法一TestAndSet指令}
• (3)^{硬件指令方法一Swap指令}

[!NOTE] 以上对TS和Swap指令的描述仅为功能描述，它们由硬件逻辑实现，不会被中断。

用硬件指令方法实现互斥的

• 优点：
  • ①简单、容易验证其正确性
  • ②适用于任意数目的进程，支持多处理器系统
  • ③支持系统中有多个临界区，只需为每个临界区设立一个布尔变量。
• 缺点：
  • ①等待进入临界区的进程会占用CPU执行while循环，不能实现“让权等待”
  • ②从等待进程中随机选择一个进程进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

2.3.3 互斥锁

解决临界区最简单的工具就是互斥锁(mutex lock)。一个进程在进入临界区时调用acquire()函数，以获得锁;在退出临界区时调用release()函数，以释放锁。每个互斥锁有一个布尔变量 available,表示锁是否可用。如果锁是可用的，调用acquire()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。其过程描述如下:

acquire(){            //获得锁的定义
  while(!available);  //忙等待
  available=false;    //获得锁
}

release(){            //释放锁的定义
  available=true;     //释放锁
}

acquire()或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

上面描述的互斥锁也称自旋锁，其主要缺点是忙等待，当有一个进程在临界区时，任何其他进程在进入临界区前必须连续循环调用acquire(。类似的还有前面介绍的单标志法、TS指令和Swap指令。当多个进程共享同一CPU时，这种连续循环显然浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上旋转，而不影响其他线程的执行。自旋锁的优点是，进程在等待锁期间，没有上下文切换，若上锁的时间较短，则等待代价不高。

2.3.4 信号量

信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的^原语 wait()和signal()访问，也可简写为P()和V(),或者简称P操作和V操作。

1. ^{整型信号量}

2. ^{记录型信号量}

3. ^{利用信号量实现进程互斥}

[!NOTE] ①对不同的临界资源需要设置不同的互斥信号量。②P(S)和V(S)必须成对出现，缺少P(S)就不能保证对临界资源的互斥访问;缺少V(S)会使临界资源永远不被释放，从而使因等待该资源而阻塞的进程永远不能被唤醒。③考试还会考查多个资源的问题，有多少资源就将信号量初值设为多少，申请资源时执行P操作，释放资源时执行V操作。

1. ^{利用信号量实现同步}

2. ^{利用信号量实现前驱关系}

3. 分析进程同步和互斥问题的方法步骤

   • 1)关系分析。找出问题中的进程数，并分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。
   • 2)整理思路。找出解决问题的关键点，并根据做过的题目找出求解的思路。根据进程的操作流程确定P操作、V操作的大致顺序。
   • 3)设置信号量。根据上面的两步，设置需要的信号量，确定初值，完善整理。

2.3.5 经典同步问题

生产者-消费者问题

问题描述：
一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区。只有当缓冲区不满时，生产者才能将消息放入缓冲区：否则必须阻塞，等待消费者从缓冲区中取出消息后将其唤醒。只有当缓冲区不空时，消费者才能从缓冲区中取出消息：否则必须等待，等待生产者将消息放入缓冲区后将其唤醒。由于缓冲区是临界资源，因此必须互斥访问。

问题分析:

• 1)关系分析。生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，它们也是同步关系。
• 2)整理思路。这里比较简单，只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步PV操作的位置。
• 3)信号量设置。信号量mutex作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量初值为1:信号量full用于记录当前缓冲池中的“满”缓冲区数,初值为0,信号量empty用于记录当前缓冲池中的“空”缓冲区数，初值为n。

生产者-消费者进程的描述如下:

semaphore mutex=1;                  //临界区互斥信号量
semaphore empty=n;                  //空闲缓冲区
semaphore full=0;                   //缓冲区初始化为空
producer(){                         //生产者进程
  while(1){
    produce an item in nextp;       //生产数据
    P(empty);(要用什么,P一下)         //获取空缓冲区单元
    P(mutex);(互斥夹紧)              //进入临界区
    add nextp to buffer;(行为)      //将数据放入缓冲区
    V(mutex);(互斥夹紧)              //离开临界区，释放互斥信号量
    V(full);(提供什么,V一下)          //满缓冲区数加1
  }
}
consumer(){                         //消费者进程
  while(1){
    P(fu11);                        //获取满缓冲区单元
    P(mutex);                       //进入临界区
    remove an item from buffer;     //从缓冲区中取出数据
    V(mutex);                       //离开临界区，释放互斥信号量
    V(empty);                       //空缓冲区数加1
    consume the item;               //消费数据
  }
}

多生产者-多消费者

问题描述:
桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果：仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

问题分析:

• 1)关系分析。由每次只能向盘中放一个水果可知，爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发，如图2.11所示。
• 2)整理思路。这里有4个进程，实际上可抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。
• 3)信号量设置。首先将信号量plate设置互斥信号量，表示是否允许向盘子放入水果，初值为1表示允许放入，且只允许放入一个。信号量apple表示盘子中是否有苹果，初值为0表示盘子为空，不许取，apple=1表示可以取。信号量orange表示盘子中是否有橘子，初值为0表示盘子为空，不许取，orange=1表示可以取。

解决该问题的代码如下:

semaphore plate=1,apple=0,orange=0;
dad(){                                      //父亲进程
  while(1){
    prepare an apple;
    P(plate);                               //互斥向盘中取、放水果
    put the apple on the plate;             //向盘中放苹果
    V(apple);                               //允许取苹果
  }
}
mom(){                                      //母亲进程
  while(1){
    prepare an orange;
    P(plate);                               //互斥向盘中取、放水果
    put the orange on the plate;            //向盘中放橘子
    V(orange);                              //允许取橘子
  }
}
son(){                                      //儿子进程
  while(1){
    P(orange);                              //互斥向盘中取橘子
    take an orange from the plate;
    V(plate);                               //允许向盘中取、放水果
    eat the orange;
  }
}
daughter(){                                 //女儿进程
  while(1){
    P(apple);                               //互斥向盘中取苹果
    take an apple from the plate;
    V(plate);                               //允许向盘中取、放水果
    eat the apple;
  }
}

进程间的关系如图2.11所示。dad()和daughter()、mom()和son()必须连续执行，正因为如此，也只能在女儿拿走苹果后或儿子拿走橘子后才能释放盘子，即V(plate)操作。

读者-写者问题

问题描述:
有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作：②只允许一个写者往文件中写信息；③任意一个写者在完成写操作之前不允许其他读者或写者工作：④写者执行写操作前，应让已有的读者和写者全部退出。

问题分析:

• 1)关系分析。由题目分析读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥问题。
• 2)整理思路。两个进程，即读者和写者。写者是比较简单的，它和任何进程互斥，用互斥信号量的P操作、V操作即可解决。读者的问题比较复杂，它必须在实现与写者互斥的同时，实现与其他读者的同步，因此简单的一对P操作、V操作是无法解决问题的。这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者时，写者是无法写文件的，此时读者会一直占用文件，当没有读者时，写者才可以写文件。同时，这里不同读者对计数器的访问也应该是互斥的。
• 3)信号量设置。首先设置信号量cout为计数器，用于记录当前读者的数量，初值为0;设置mutex为互斥信号量，用于保护更新count变量时的互斥：设置互斥信号量rw,用于保证读者和写者的互斥访问。

代码如下:

int count = 0;                      //用于记录当前的读者数量
semaphore mutex = 1;                //用于保护更新count变量时的互斥
semaphore rw = 1;                   //用于保证读者和写者互斥地访问文件
writer(){                           //写者进程
  while(1){
    P(rw);                          //互斥访问共享文件
    writing;                        //写入
    V(rw);                          //释放共享文件
  }
}
reader(){                           //读者进程
  while(1){
    P(mutex);                       //互斥访问count变量
    if(count == 0)                  //当第一个读进程读共享文件时
      P(rw);                        //阻止写进程写
    count++;                        //读者计数器加1
    V(mutex);                       //释放互斥变量count
    reading;                        //读取
    P(mutex);                       //互斥访问count变量
    count--;                        //读者计数器减1
    if(count==0)                    //当最后一个读进程读完共享文件
      V(rw);                        //允许写进程写
    V(mutex);                       //释放互斥变量count
  }
}

在上面的算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并在上面程序的writer()和reader()函数中各增加一对PV操作，就可以得到写进程优先的解决程序。

int count = 0;                      //用于记录当前的读者数量
semaphore mutex = 1;                //用于保护更新count变量时的互斥
semaphore rw = 1;                   //用于保证读者和写者互斥地访问文件
semaphore w = 1;                    //用于实现“写优先”
writer(){                           //写者进程
  while(1){
    P(w);                           //在无写进程请求时进入
    P(rw);                          //互斥访问共享文件
    writing;                        //写入
    V(rw);                          //释放共享文件
    V(w);                           //恢复对共享文件的访问
  }
}
reader(){                           //读者进程
  while(1){
    P(w);                           //在无写进程请求时进入
    P(mutex);                       //互斥访问count变量
    if(count == 0)                  //当第一个读进程读共享文件时
      P(rw);                        //阻止写进程写
    count++;                        //读者计数器加1
    V(mutex);                       //释放互斥变量count
    V(w);                           //恢复对共享文件的访问
    reading;                        //读取
    P(mutex);                       //互斥访问count变量
    count--;                        //读者计数器减1
    if(count==0)                    //当最后一个读进程读完共享文件
      V(rw);                        //允许写进程写
    V(mutex);                       //释放互斥变量count
  }
}

这里的写进程优先是相对而言的，有些书上将这个算法称为读写公平法，即读写进程具有一样的优先级。当一个写进程访问文件时，若先有一些读进程要求访问文件，后有另一个写进程要求访问文件，则当前访问文件的进程结束对文件的写操作时，会是一个读进程而不是一个写进程占用文件(在信号量w的阻塞队列上，因为读进程先来，因此排在阻塞队列队首，而V操作唤醒进程时唤醒的是队首进程)，所以说这里的写优先是相对的，想要了解如何做到真正写者优先，可参考其他相关资料。

读者-写者问题有一个关键的特征，即有一个互斥访问的计数器count,因此遇到一个不太好解决的同步互斥问题时，要想一想用互斥访问的计数器count能否解决问题。

哲学家进餐问题

问题描述:
一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭，如图2.12所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子己在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。

问题分析:

• 1)关系分析。5名哲学家与左右邻居对其中间筷子的访问是互斥关系。
• 2)整理思路。显然，这里有5个进程。本题的关键是如何让一名哲学家拿到左右两根筷子而不造成死锁或饥饿现象。解决方法有两个:一是让他们同时拿两根筷子;二是对每名哲学家的动作制定规则，避免饥饿或死锁现象的发生。
• 3)信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1},用于对5个筷子的互斥访问。哲学家按顺序编号为0~4，哲学家i左边筷子的编号为i,哲学家右边筷子的编号为(i+1)%5。

semaphore chopsticks[5] = {1,1,1,1,1};                //定义信号量数组chopstick[5],并初始化
Pi(){                                                 //i号哲学家的进程
  do{
    P(chopstick[i]);                                  //取左边筷子
    P(chopstick[(i+1)%5]);                            //取右边筷子
    eat;                                              //进餐
    V(chopstick[i]);                                  //放回左边筷子
    V(chopstick[(i+1)%5]);                            //放回右边筷子
    think;                                            //思考
  }while(1);
}

该算法存在以下问题:当5名哲学家都想要进餐并分别拿起左边的筷子时(都恰好执行完 wait(chopstick[i]);)筷子已被拿光,等到他们再想拿右边的筷子时(执行wait(chopstick[ (i+1)%5]);)就全被阻塞，因此出现了死锁。
为防止死锁发生，可对哲学家进程施加一些限制条件，比如至多允许4名哲学家同时进餐:仅当一名哲学家左右两边的筷子都可用时,才允许他抓起筷子;对哲学家顺序编号,要求奇数号哲学家先拿左边的筷子,然后拿右边的筷子,而偶数号哲学家刚好相反。
制定的正确规则如下:假设采用第二种方法,当一名哲学家左右两边的筷子都可用时,才允许他抓起筷子。

semaphore chopsticks[5] = {1,1,1,1,1};                //定义信号量数组chopstick[5],并初始化
semaphore mutex = 1;                                  //设置取筷子的信号量
Pi(){                                                 //i号哲学家的进程
  do{
    P(mutex);                                         //在取筷子前获得互斥量
    P(chopstick[i]);                                  //取左边筷子
    P(chopstick[(i+1)%5]);                            //取右边筷子
    V(mutex);                                         //释放取筷子的信号量
    eat;                                              //进餐
    V(chopstick[i]);                                  //放回左边筷子
    V(chopstick[(i+1)%5]);                            //放回右边筷子
    think;                                            //思考
  }while(1);
}

^ps1

吸烟者问题

问题描述:
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就将另外两种材料放到桌上，如此重复（让三个抽烟者轮流地抽烟）。

问题分析:

• 1)关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或以上的抽烟者，三个抽烟者对抽烟这个动作互斥（或由三个抽烟者轮流抽烟得知）。
• 2)整理思路。显然这里有4个进程。供应者作为生产者向三个抽烟者提供材料。
• 3)信号量设置。信号量offer1,.offer2,offer3分别表示烟草和纸组合的资源、烟草和胶水组合的资源、纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作。

代码如下:

int num = 0;                                  //存储随机数
semaphore offer1 = 0;                         //定义信号量对应烟草和纸组合的资源
semaphore offer2 = 0;                         //定义信号量对应烟草和胶水组合的资源
semaphore offer3 = 0;                         //定义信号量对应纸和胶水组合的资源
semaphore finish = 0;                         //定义信号量表示抽烟是否完成
process P1(){                                 //供应者
  while(1){
    num++;
    num = num % 3;
    if(num == 0)
      V(offer1)                               //提供烟草和纸
    else if(num == 1)
      V(offer2)                               //提供烟草和胶水
    else
      V(offer3)                               //提供纸和胶水
    任意两种材料放在桌子上;
    P(finish);
  }
}

process P2(){                                 //拥有烟草者
  while(1){
    P(offer3);
    拿纸和胶水，卷成烟，抽掉;
    V(finish);
  }
}
process P3(){                                 //拥有纸者
  while(1){
    P(offer2);
    拿烟草和胶水,卷成烟,抽掉;
    V(finish);
  }
}
process P4(){                                 //拥有胶水者
  while(1){
    P(offer1);
    拿烟草和纸,卷成烟,抽掉;
    V(finish);
  }
}

2.3.6 管程

在信号量机制中，每个要访问临界资源的进程都必须自备同步的PV操作，大量分散的同步操作给系统管理带来了麻烦，且容易因同步操作不当而导致系统死锁。于是，便产生了一种新的进程同步工具一一管程。管程的特性保证了进程互斥，无须程序员自己实现互斥，从而降低了死锁发生的可能性。同时管程提供了条件变量，可以让程序员灵活地实现进程同步。

1. ^{管程的定义}

由上述定义可知，管程由4部分组成:

• ①管程的名称
• ②局部于管程内部的共享数据结构说明
• ③对该数据结构进行操作的一组过程（或函数）
• ④对局部于管程内部的共享数据设置初始值的语句。

管程的定义描述举例如下:

monitor Demo{                     //①定义一个名称为Demo的管程
  //②定义共享数据结构，对应系统中的某种共享资源
  共享数据结构S;
  //④对共享数据结构初始化的语句
  init_code(){
    S = 5;                        //初始资源数等于5
  }
  take_away(){                    //③过程1:申请一个资源
    对共享数据结构x的一系列处理;
    S--;                          //可用资源数-1
    ...
  }
  give_back(){                    //③过程2：归还一个资源
    对共享数据结构x的一系列处理;
    S++;                          //何用资源数+1
    ...
  }
}

熟悉面向对象程序设计的读者看到管程的组成后，会立即联想到管程很像一个类(class)。

• 1)管程将对共享资源的操作封装起来，管程内的共享数据结构只能被管程内的过程所访问。一个进程只有通过调用管程内的过程才能进入管程访问共享资源。对于上例，外部进程只能通过调用take_away()过程来申请一个资源：归还资源也类似。

• 2)每次仅允许一个进程进入管程，从而实现进程互斥。若多个进程同时调用take_away(), give_back(),则只有某个进程运行完它调用的过程后，下一进程才能开始运行它调用的过程。即各进程只能串行执行管程内的过程，这一特性保证了进程互斥访问S。

• ^条件变量

• x.wait:当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程。此时其他进程可以使用该管程。

• x.signal:x对应的条件发生了变化，则调用x.signal,唤醒一个因x条件而阻塞的进程。

下面给出条件变量的定义和使用:

monitor Demo{
  共享数据结构S;
  condition x;                     //定义一个条件变量x
  init_code(){ ... }
  take_away(){
    if(S <= 0) x.wait()            //资源不够,在条件变量x上阻塞等待
    资源足够,分配资源,做一系列相应处理;
  }
  give_back(){
    归还资源,做一系列相应处理;
    if(有进程在等待) x.signal();     //唤醒一个阻塞进程
  }
}

条件变量和信号量的比较:

• 相似点:条件变量的wait/signal操作类似于信号量的P/V操作，可以实现进程的阻塞/唤醒。
• 不同点:条件变量是“没有值”的，仅实现了“排队等待”功能：而信号量是“有值”的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。

2.3.7 本节小结

1. 为什么要引入进程同步的概念？

在多道程序共同执行的条件下，进程与进程是并发执行的，不同进程之间存在不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。

1. 不同的进程之间会存在什么关系？

进程之间存在同步与互斥的制约关系。
同步是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。
互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

1. 当单纯用本节介绍的方法解决这些问题时会遇到什么新的问题吗？

当两个或两个以上的进程在执行过程中，因占有一些资源而又需要对方的资源时，会因为争夺资源而造成一种互相等待的现象，若无外力作用，它们都将无法推进下去。这种现象称为死锁，具体介绍和解决方案请参考下一节。

2.3.8本节习题精选

一、单项选择题

36.

A.z=1,-3;c=-1,9 B.z=-1,3;c=1,9 C.z=-1,3;c=9 D.z=3;c=1,9

B

---

本题的关键是，输出语句A2,B2中读取的x的值不同，由于A1,B1执行有先后问题，使得在执行A2,B2前，x的可能取值有两个，即1,-3;这样，输出z的值可能是1+2=3或(-3)+2=-1;输出c的值可能是1×1=1或(-3)×(-3)=9。

39. 其中，(1)和(2)处的代码分别为()。

A.turn=0,turn=0 B.turn=0,turn=1 C.turn=1,turn=0 D.turn=1,turn=1

C

---

根据Peterson算法的原理，可知(1)和(2)处分别为turn=1和turn=0。

44.下列关于生产者-消贵者问题的唤醒操作的说法中，正确的是()。

49.

A.0 B.1 C.4 D.5

C

---

信号量seat表示桌子上可以坐下的位置数，由于只有五个位置，所以每次只能有四位哲学家同时拿起左边的餐叉，才能保证不会发生死锁，所以seat的初值应该为4。

50.

A.5,9,9 B.5,9,4 C.5,12,9 D.5,12,4

C

---

52.

A.不能保证进程互斥进入临界区，会出现“饥饿”现象 B.不能保证进程互斥进入临界区，不会出现“饥饿”现象 C.能保证进程互斥进入临界区，会出现“饥饿”现象 D.能保证进程互斥进入临界区，不会出现“饥饿”现象

D

---

这是Peterson算法的实际实现，保证进入临界区的进程合理安全。
该算法为了防止两个进程为进入临界区而无限期等待,设置了变量turn,表示允许进入临界区的编号,每个进程在先设置自己的标志后再设置turn标志,允许另一个进程进入。这时，再同时检测另一个进程状态标志和允许进入标志，就可保证当两个进程同时要求进入临界区时只允许一个进程进入临界区。保存的是较晚的一次赋值，因此较晚的进程等待，较早的进程进入。先到先入，后到等待，从而完成临界区访问的要求。
其实这里可想象为两个人进门，每个人进门前都会和对方客套一句“你走先”。若进门时没别人，就当和空气说句废话，然后大步登门入室：若两人同时进门，就互相先请，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大地进门。

53.

A.可能为-1或3 B.只能为1 C.可能为0,1或2 D.可能为-1,0,1或2

C

---

x的值最终是多少，取决于最后是哪个进程对x进行了写操作。一个进程一旦拿到了x值，它最后对x写操作的值也就确定了。所以本题只需考虑两个进程拿到ⅹ值的所有可能情况。对于P1进程，最初取到的x值可能是1，也可能是P2进程完成后更新得到的x值0，因此对于P1进程，最终写入x的值可能是2（当它最初取到1时）和1（当它最初取到0时）。同理，对于P2进程，最初取到的x值可能是1，也可能是P1进程完成后更新得到的x值2，因此对于P2进程，最终写入x的值有可能是0（当它最初取到1时）和1（当它最初取到2时）。因此，最终的x值可能是0、1或2。

54.【2016统考真题】进程P1和P2均包含并发执行的线程，部分伪代码描述如下所示。

A.a=1与a=2 B.a=x与b=x C.x+=1与x+=2 D.x+=1与x+=3

C

---

需要进行互斥的操作是对临界资源的访问，也就是说，不同线程对同一个进程内部的共享变量的访问才有可能需要进行互斥，不同进程的线程、代码段或变量不存在互斥访问的问题，同一个线程内部的局部变量也不存在互斥访问的问题。选项A中的是线程内部的局部变量，不需要互斥访问。选项D是不同进程的线程代码段，不存在互斥访问的问题。选项B是对进程内部的共享变量x的读操作，不互斥也不影响执行结果，所以不需要互斥访问。选项C是不同线程对同一个进程内部的共享变量的写操作，需要互斥访问（类似于读者-写者问题）。

55.

A.退出临界区的进程负责唤醒阻塞态进程 B.等待进入临界区的进程不会主动放弃CPU C.上述伪代码满足“让权等待”的同步准则 D.while(TSL(&lock))语句应在关中断状态下执行

B

---

使用TSL指令实现进程互斥时，并没有阻塞态进程，等待进入临界区的进程一直停留在执行 while(TSL(&lock))的循环中，不会主动放弃CPU,一直处于运行态，直到该进程的时间片用完放弃处理机，转为就绪态，此时切换另一个就绪态进程占用处理机。这不同于信号量机制实现的互斥。由此可知A和C错误，B正确。TSL指令本身就是原子操作，不需要关中断来保证其不被打断。TSL指令实现原子性的原理是，执行TSL指令的CPU锁住内存总线，以禁止其他CPU在本指令结束之前访问内存。此外，假如while(TSL(&Iock))在关中断状态下执行，若TSL(&lock)一直为true,不再开中断，则系统可能因此终止。因此D错误。

57.

A.1 B.2 C.3 D.4

B

---

仔细阅读两个线程代码可知，thread1和thread2均是对x进行加1操作，x的初始值为0，若要使得最终x=2,只能先执行完thread1再执行thread2,或先执行完thread2再执行thread1,因此仅有2种可能。

二、综合应用题

01.下面是两个并发执行的进程，它们能正确运行吗？若不能请举例说明并改正。

02.在一个仓库中可以存放A和B两种产品，要求:
①每次只能存入一种产品。
②A产品数量-B产品数量 < M,其中M是正整数。
③B产品数量-A产品数量 < N,其中N是正整数。
假设仓库的容量是无限的，试用P,V操作描述产品A和B的入库过程。

03.面包师有很多面包，由名销售人员推销。每名顾客进店后按序取一个号，并且等待叫号，当一名销售人员空闲时，就按序叫下一个号。可以用两个整型变量来记录当前的取号值和叫号值，试设计一个使销售人员和顾客同步的算法。

04.

05.某寺庙有小和尚、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3个。每次入缸取水仅为1桶水，且不可同时进行。试给出有关从缸取水、入水的算法描述。

06.

07.

08.

09.

10.设P,Q,R共享一个缓冲区，P,Q构成一对生产者-消费者，R既为生产者又为消费者，若缓冲区为空，则可以写入：若缓冲区不空，则可以读出。使用PV操作实现其同步。

11.理发店里有一位理发师、一把理发椅和把供等候理发的顾客坐的椅子。若没有顾客，理发师便在理发椅上睡觉，一位顾客到来时，顾客必须叫醒理发师，若理发师正在理发时又有顾客来到，若有空椅子可坐，则坐下来等待，否则就离开。试用P,V操作实现，并说明信号量的定义和初值。

12.假设一个录像厅有1,2,3三种不同的录像片可由观众选择放映，录像厅的放映规则如下:
1)任意时刻最多只能放映一种录像片，正在放映的录像片是自动循环放映的，最后一名观众主动离开时结束当前录像片的放映。
2)选择当前正在放映的录像片的观众可立即进入，允许同时有多位选择同一种录像片的观众同时观看，同时观看的观众数量不受限制。
3)等待观看其他录像片的观众按到达顺序排队，当一种新的录像片开始放映时，所有等待观看该录像片的观众可依次序进入录像厅同时观看。用一个进程代表一个观众，要求:用信号量方法PV操作实现，并给出信号量定义和初始值。

13.设公共汽车上驾驶员和售票员的活动分别如下图所示。驾驶员的活动：启动车辆，正常行车，到站停车；售票员的活动：关车门，售票，开车门。在汽车不断地到站、停车、行驶的过程中，这两个活动有什么同步关系？用信号量和P,V操作实现它们的同步。

14.

15.

16.假设有3个抽烟者和1个供应者。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者无限提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就将另外两种材料放到桌上，如此重复，让3个抽烟者轮流抽烟。

17.

18.

19.

20.【2014统考真题】系统中有多个生产者进程和多个消贵者进程，共享一个能存放1000件产品的环形缓冲区（初始为空）。缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；缓冲区未空时，消费者进程可从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品。请使用信号量P,V(wait(),signal())操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。

21.

22.

23.【2019统考真题】有n(n≥3)名哲学家围坐在一张圆桌边，每名哲学家交替地就餐和思考。在圆桌中心有m(m≥1)个碗，每两名哲学家之间有一根筷子。每名哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的P,V操作(wait(),signal()操作)描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。

24.【2020统考真题】现有5个操作A、B、C、D和E,操作C必须在A和B完成后执行，操作E必须在C和D完成后执行，请使用信号量的wait()、signal()操作(P、V操作)描述上述操作之间的同步关系，并说明所用信号量及其初值。

25.

26.

27.

2.4 死锁

2.4.1 死锁的概念

1. ^{死锁的定义}
2. ^{死锁与饥饿}

死锁和饥饿

• 共同点:进程无法顺利向前推进的现象。
• 主要差别:
  • ①发生饥饿的进程可以只有一个：而死锁是因循环等待对方手里的资源而导致的，因此，如果有死锁现象，那么发生死锁的进程必然大于或等于两个。
  • ②发生饥饿的进程可能处于就绪态（长期得不到CPU,如SJF算法的问题），也可能处于阻塞态(如长期得不到所需的I/O设备，如上述举例);而发生死锁的进程必定处于阻塞态。

1. 死锁产生的原因
   1. ^{系统资源的竞争}
   2. ^{进程推进顺序非法}

信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息，也会使得这些进程无法继续向前推进。例如，进程A等待进程B发的消息，进程B又在等待进程A发的消息，可以看出进程A和B不是因为竞争同一资源，而是在等待对方的资源导致死锁。

1. 死锁产生的必要条件(产生死锁必须同时满足以下4个条件)
   1. ^互斥条件
   2. ^{不可剥夺条件}
   3. ^{请求并保持条件}
   4. ^{循环等待条件}

直观上看，循环等待条件似乎和死锁的定义一样，其实不然。按死锁定义构成等待环所要求的条件更严，它要求P_i,等待的资源必须由P_i+1来满足，而循环等待条件则无此限制。例如，系统中有两台输出设备，P₀和P_K各占有一台，且K不属于集合{0,1，…，n}。P_n等待一台输出设备，它可从P₀或P_K获得。因此，虽然P_n,P₀和其他一些进程形成了等待环，但P_K不在圈内，若P_K释放了输出设备，则可打破循环等待，如图2.14所示。因此循环等待只是死锁的必要条件。

资源分配图含圈而系统又不一定有死锁的原因是，同类资源数大于1。但若系统中每类资源都只有一个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件。
要注意区分不可剥夺条件与请求并保持条件。下面用一个简单的例子进行说明：若你手上拿着一个苹果（即便你不打算吃），别人不能将你手上的苹果拿走，则这就是不可剥夺条件：若你左手拿着一个苹果，允许你右手再去拿一个苹果，则这就是请求并保持条件。

1. 死锁的处理策略
   1. ^死锁预防
   2. ^避免死锁
   3. ^{死锁的检测及解除}

预防死锁和避免死锁都属于事先预防策略，预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低;避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。

死锁的几种处理策略的比较见表2.4。

2.4.2 死锁预防

预防死锁的发生只需破坏死锁产生的4个必要条件之一即可。

1. ^{破坏互斥条件}
2. ^{破坏不可剥夺条件}
3. 破坏请求并保持条件
   1. 采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源。在它的资源未满足前，不让它投入运行。在进程的运行期间，不会再提出资源请求，从而破坏“请求”条件。在等待期间，进程不占有任何资源，从而破坏了“保持”条件。
   2. 允许进程只获得运行初期所需的资源后，便可开始运行。进程在运行过程中再逐步释放已分配给自己且已使用完毕的全部资源后，才能请求新的资源。

方法一的实现简单，但缺点也显而易见，系统资源被严重浪费，其中有些资源可能仅在运行初期或快结束时才使用。而且还会导致“饥饿”现象，由于个别资源长期被其他进程占用，将导致等待该资源的进程迟迟不能开始运行。方法二则改进了这些缺点。

1. ^{破坏循环等待条件}

2.4.3 死锁避免

避免死锁同样属于事先预防策略，但并不是事先采取某种限制措施破坏死锁的必要条件，而是在每次分配资源的过程中，都要分析此次分配是否会带来死锁风险，只有在不产生死锁的情况下，系统才会为其分配资源。这种方法所施加的限制条件较弱，可以获得较好的系统性能。

1. 系统安全状态

避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配;否则让进程等待。

所谓安全状态，是指系统能按某种进程推进顺序(P1,P2,...,Pn)为每个进程P,分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成。此时称P1,P2,...,Pn为安全序列（可能有多个）。若系统无法找到一个安全序列，则称系统处于不安全状态。

命题追踪:系统安全状态的分析(2018)

如果系统处于安全状态，则一定不会发生死锁：若系统进入不安全状态，则有可能发生死锁(处于不安全状态未必发生死锁，但发生死锁时一定是处于不安全状态)。

1. 银行家算法

银行家算法是最著名的死锁避免算法，其思想是：将操作系统视为银行家，操作系统管理的资源视为银行家管理的资金，进程请求资源相当于用户向银行家贷款。进程运行之前先声明对各种资源的最大需求量，其数目不应超过系统的资源总量。当进程在运行中申请资源时，系统必须先确定是否有足够的资源分配给该进程。若有，再进一步试探在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。

(1)数据结构描述 (2)银行家算法描述 (3)安全性算法

1. 安全性算法举例

1. 银行家算法举例

2.4.4 死锁检测和解除

前面介绍的死锁预防和避免算法，都是在为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不采取任何预防或避免措施，则应该提供死锁检测和解除的手段。

1. 死锁检测

命题追踪:多在资源竞争时发生死锁的临界条件分析(2016、2021)

[!NOTE] S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。

1. 死锁解除
   1. ^{资源剥夺法}
   2. ^{撤销进程法}
   3. ^{进程回退法}

[!NOTE] 在资源分配图中，用死锁定理化简后，还有边相连的那些进程就是死锁进程

2.4.5 本节小结

1. 为什么会产生死锁？产生死锁有什么条件？ 由于系统中存在一些不可剥夺资源，当两个或两个以上的进程占有自身的资源并请求对方的资源时，会导致每个进程都无法向前推进，这就是死锁。死锁产生的必要条件有4个，分别是互斥条件、不剥夺条件、请求并保持条件和循环等待条件。
   互斥条件是指进程要求分配的资源是排他性的，即最多只能同时供一个进程使用。
   不剥夺条件是指进程在使用完资源之前，资源不能被强制夺走。
   请求并保持条件是指进程占有自身本来拥有的资源并要求其他资源。
   循环等待条件是指存在一种进程资源的循环等待链。

2. 有什么办法可以解决死锁问题？ 死锁的处理策略可以分为预防死锁、避免死锁及死锁的检测与解除。
   死锁预防是指通过设立一些限制条件，破坏死锁的一些必要条件，让死锁无法发生。
   死锁避免指在动态分配资源的过程中，用一些算法防止系统进入不安全状态，从而避免死锁。
   死锁的检测和解除是指在死锁产生前不采取任何措施，只检测当前系统有没有发生死锁，若有，则采取一些措施解除死锁。

2.4.6 本节习题精选

一、单项选择题

23.

A.进程不会死锁，也不会“饥饿” B.进程不会死锁，但是会“饥饿” C.进程会死锁，但是不会“饥饿” D.进程会死锁，也会“饥饿”

---

24.

A.程序能正确运行，结果唯一 B.程序不能正确运行，可能有两种结果 C.程序不能正确运行，结果不确定 D.程序不能正确运行，可能会死锁

---

26.

A.Ⅰ、Ⅱ、Ⅳ B.Ⅰ、Ⅱ C.仅Ⅰ D.Ⅰ、Ⅲ

---

33.【2011统考真题】某时刻进程的资源使用情况见下表，此时的安全序列是()。

A.P1,P2,P3,P4 B.P1,P3,P2,P4 C.P1,P4,P3,P2 D.不存在

---

34.

A.P0,P2,P4,P1,P3 B.P1,P0,P3,P4,P2 C.P2,P1,P0,P3,P4 D.P3,P4,P2,P1,P0

---

41.

A.存在安全序列P1、P2、P3 B.存在安全序列P2、P1、P3 C.存在安全序列P2、P3、P1 D.不存在安全序列

---

43.【2022统考真题】系统中有三个进程P0、P1、P2及三类资源A、B、C。若某时刻系统分配资源的情况如下表所示，则此时系统中存在的安全序列的个数为()。

A.1 B.2 C.3 D.4

---

二、综合应用题

03.

04.

05.

06.

07.

08.

09.

2.5 本章疑难点

1. 进程与程序的区别与联系
   1. 进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念。进程的运行实体是程序，离开程序的进程没有存在的意义。从静态角度看，进程是由程序、数据和进程控制块(PCB)三部分组成的。而程序是一组有序的指令集合，是一种静态的概念。
   2. 进程是程序的一次执行过程，它是动态地创建和消亡的，具有一定的生命周期，是暂时存在的;而程序则是一组代码的集合，是永久存在的，可长期保存。
   3. 一个进程可以执行一个或几个程序，一个程序也可构成多个进程。进程可创建进程，而程序不可能形成新的程序。
   4. 进程与程序的组成不同。进程的组成包括程序、数据和PCB。
2. 银行家算法的工作原理 银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，若有则先进行试分配，并对分配后的新状态进行安全性检查。若新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样，它保证系统始终处于安全状态，从而避免了死锁现象的发生。
3. 进程同步、互斥的区别和联系 并发进程的执行会产生相互制约的关系：一种是进程之间竞争使用临界资源，只能让它们逐个使用，这种现象称为互斥，是一种竞争关系;另一种是进程之间协同完成任务，在关键点上等待另一个进程发来的消息，以便协同一致，是一种协作关系。

脚注分界线

^{进程回退法}. 让一个或多个死锁进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺。要求系统保持进程的历史信息，设置还原点。 ↩

^{撤销进程法}. 强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。这种方式实现简单，但付出的代价可能很大，因为有些进程可能已经接近结束，一旦被终止，以后还得从头再来。 ↩

^{资源剥夺法}. 挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。 ↩

^{破坏循环等待条件}. 为了破坏循环等待条件，可以采用顺序资源分配法。首先给系统中的各类资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（编号相同的资源）一次申请完。也就是说，一个进程只在已经占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能再逆向申请小编号的资源，因此不会产生循环等待的现象。
这种方法的缺点：编号必须相对稳定，因此不便于增加新类型设备：尽管在编号时已考虑到大多数进程使用这些资源的顺序，但是进程实际使用资源的顺序还是可能和编号的次序不一致，这就会造成资源的浪费;此外，必须按规定次序申请资源，也会给用户编程带来麻烦。 ↩

^{破坏不可剥夺条件}. 当一个已经保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，进程已占有的资源会被暂时释放，或者说是被剥夺了，从而破坏了不可剥夺条件。
该策略实现起来比较复杂。释放已获得的资源可能造成前一阶段工作的失效，因此这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。反复地申请和释放资源既影响进程推进速度，又增加系统开销，进而降低系统吞吐量。 ↩

^{破坏互斥条件}. 如果将只能互斥使用的资源改造为允许共享使用，那么系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且为了系统安全，很多时候还必须保护这种互斥性。 ↩

^{死锁的检测及解除}. 无须采取任何限制性措施，允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。 ↩

^避免死锁. 在资源的动态分配过程中，用某种方法防止系统进入不安全状态。 ↩

^死锁预防. 设置某些限制条件，破坏产生死锁的4个必要条件中的一个或几个。 ↩

^{循环等待条件}. 存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待态的进程集合{P₁,P₂,…,P_n},其中P,等待的资源被 P_i+1(i=0,1,…,n-1)占有，P_n等待的资源被P₀占有，如图2.13所示。 ↩

^{请求并保持条件}. 进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。 ↩

^{不可剥夺条件}. 进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放）。 ↩

^互斥条件. 进程要求对所分配的资源（如打印机）进行排他性使用，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。 ↩

^{进程推进顺序非法}. 请求和释放资源的顺序不当，也同样会导致死锁。例如，进程P,P2分别保持了资源R,R2,而P,申请资源R2、P2申请资源R,时，两者都会因为所需资源被占用而阻塞，于是导致死锁。 ↩

^{系统资源的竞争}. 通常系统中拥有的不可剥夺资源（如磁带机、打印机等），其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源（如CPU和主存）的竞争是不会引起死锁的。 ↩

^{死锁与饥饿}. 一组进程处于死锁状态是指组内的每个进程都在等待一个事件，而该事件只可能由组内的另一个进程产生。与死锁相关的另一个问题是饥饿，即进程在信号量内无穷等待的情况。
产生饥饿的主要原因是：当系统中有多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序，有的分配策略可能是不公平的，即不能保证等待时间上界的存在。在这种情况下，即使系统未发生死锁，某些进程也可能长时间等待。当等待时间给进程的推进带来明显影响时，称发生了饥饿。例如，当有多个进程需要打印文件时，若系统分配打印机的策略是最短文件优先，则长文件的打印任务将因短文件的源源不断到来而被无限期推迟，最终导致饥饿，甚至“饿死”。饥饿并不表示系统一定死锁，但至少有一个进程的执行被无限期推迟。 ↩

^{死锁的定义}. 在多道程序系统中，由于进程的并发执行，极大提升了系统效率。然而，多个进程的并发执行也带来了新的问题一一死锁。所谓死锁，是指多个进程因竞争资源而造成的一种僵局（互相等待对方手里的资源)，使得各个进程都被阻塞，若无外力干涉，这些进程都无法向前推进。 ↩

^条件变量. 当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程。为此，将阻塞原因定义为条件变量condition。通常，一个进程被阻塞的原因可以有多个，因此在管程中设置了多个条件变量。每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程，对条件变量只能进行两种操作，即wait和signal。. ↩

^{管程的定义}. 系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。利用共享数据结构抽象地表示系统中的共享资源，而将对该数据结构实施的操作定义为一组过程。进程对共享资源的申请、释放等操作，都通过这组过程来实现，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程(monitor)。管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。 ↩

^ps1. 熟悉ACM或有过相关训练的读者都应知道贪心算法，哲学家进餐问题的思想其实与贪心算法的思想截然相反，贪心算法强调争取眼前认为最好的，而不考虑后续会有什么后果。若哲学家进餐问题用贪心算法来解决，即只要眼前有筷子能拿起就拿起的话，就会出现死锁。然而，若不仅考虑眼前的一步，而且考虑下一步，即不因为有筷子能拿起就拿起，而考虑能不能一次拿起两根筷子才做决定的话，就会避免死锁问题，这就是哲学家进餐问题的思维精髓。
大部分习题和真题用消费者-生产者模型或读者-写者问题就能解决，但对哲学家进餐问题仍然要熟悉。考研复习的关键在于反复多次和全面，“偷工减料”是要吃亏的。 ↩

^{利用信号量实现前驱关系}. ↩

^{利用信号量实现同步}. ↩

^{利用信号量实现进程互斥}. ↩

^{记录型信号量}. ↩

^{整型信号量}. ↩

^原语. 原语是指完成某种功能且不被分割、不被中断执行的操作序列，通常可由硬件来实现。例如，前述的TS指令和Swap指令就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机上可由软件通过屏蔽中断方法实现。原语之所以不能被中断执行，是因为原语对变量的操作过程若被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。 ↩

^{硬件指令方法一Swap指令}. Swap指令的功能是交换两个字(字节)的内容。其功能描述如下: ↩

^{硬件指令方法一TestAndSet指令}. 借助一条硬件指令一TestAndSet指令(简称TS指令)实现互斥，这条指令是原子操作。其功能是读出指定标志后将该标志设置为真。指令的功能描述如下:当用TS指令管理临界区时，为每个临界资源设置一个共享布尔变量1oCk,表示该资源的两种状态：rue表示正被占用(已加锁)：false表示空闲(未加锁)，初值为false,所以可将1lock视为一把锁。进程在进入临界区之前，先用TS指令检查lock值：①若为flse,则表示没有进程在临界区，可以进入，并将lock置为tue,这意味着关闭了临界资源(加锁)，使任何进程都不能进入临界区：②若为tu,则表示有进程在临界区中，进入循环等待，直到当前访问临界区的进程退出时解锁(将lock置为false)。利用TS指令实现互斥的过程描述如下：相比于软件实现方法，TS指令将“加锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。相比于关中断方法，由于“锁”是共享的，这种方法适用于多处理器系统。缺点是，暂时无法进入临界区的进程会占用CPU循环执行TS指令，因此不能实现“让权等待”。 ↩

^{中断屏蔽方法}. 当一个进程正在执行它的临界区代码时，防止其他进程进入其临界区的最简单方法是关中断。因为CPU只在发生中断时起进程切换，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完，进而保证互斥的正确实现，然后执行开中断。其典型模式为这种方法的缺点：①限制了CPU交替执行程序的能力，因此系统效率会明显降低。②对内核来说，在它执行更新变量的几条指令期间，关中断是很方便的，但将关中断的权限交给用户则很不明智，若一个进程关中断后不再开中断，则系统可能会因此终止。③不适用于多处理器系统，因为在一个CPU上关中断并不能防止进程在其他CPU上执行相同的临界区代码。 ↩

^{软件实现方法}. 在进入区设置并检查一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。 ↩

^互斥. 互斥也称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。 ↩

^同步. 同步亦称直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要协调它们的运行次序而等待、传递信息所产生的制约关系。同步关系源于进程之间的相互合作。 ↩

^临界资源. 虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所用，我们将一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。 ↩

^{多级队列调度算法}. 该算法在系统中设置多个就绪队列,将不同类型或性质的进程固定分配到不同的就绪队列。每个队列可实施不同的调度算法,因此,系统针对不同用户进程的需求,很容易提供多种调度策略。同一队列中的进程可以设置不同的优先级,不同的队列本身也可以设置不同的优先级。在多 CPU系统中,可以很方便为每个CPU设置一个单独的就绪队列,每个CPU可实施各自不同的调度策略,这样就能根据用户需求将多个线程分配到一个或多个CPU上运行。 ↩

^{时间片轮转(RR)调度算法}. 在这种算法中,系统将所有的就绪进程按 FCFS策略排成一个就绪队列。系统可设置每隔一定的时间(如30ms)便产生一次时钟中断,激活调度程序进行调度,将CPU分配给就绪队列的队首进程,并令其执行一个时间片。在执行完一个时间片后,即使进程并未运行完成,它也必须释放出(被剥夺)CPU给就绪队列的新队首进程,而被剥夺的进程返回到就绪队列的末尾重新排队,等候再次运行。在R调度算法中,若一个时间片尚未用完而当前进程已运行完成,则调度程序会被立即激活;若一个时间片用完,则产生一个时钟中断,由时钟中断处理程序来激活调度程序。 ↩

^{I/O型进程>计算型进程}. 所谓I/O型进程,是指那些会频繁使用I/O设备的进程,而计算型进程是那些频繁使用CPU的进程(很少使用I/O设备)。我们知道,I/O设备(如打印机)的处理速度要比CPU慢得多,因此若将I/O型进程的优先级设置得更高,就更有可能让I/O设备尽早开始工作,进而提升系统的整体效率。 ↩

^{交互型进程>非交互型进程}. 大家平时在使用手机时,在前台运行的正在和你交互的进程应该更快速地响应你,因此自然需要被优先处理。 ↩

^{系统进程>用户进程}. 系统进程作为系统的管理者,理应拥有更高的优先级。 ↩

^{动态优先级}. 创建进程时先赋予进程一个优先级,但优先级会随进程的推进或等待时间的增加而改变,以便获得更好的调度性能。例如,规定优先级随等待时间的增加而提高,于是,对于优先级初值较低的进程,等待足够长的时间后也可获得CPU。 ↩

^{静态优先级}. 优先级是在创建进程时确定的,且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。优点是简单易行,系统开销小：缺点是不够精确,可能出现优先级低的进程长期得不到调度的情况。 ↩

^{优先级调度算法}. 优先级调度算法既可用于作业调度,又可用于进程调度。该算法中的优先级用于描述作业的紧迫程度。在作业调度中,优先级调度算法每次从后备作业队列中选择优先级最高的一个或几个作业,将它们调入内存,分配必要的资源,创建进程并放入就绪队列。在进程调度中,优先级调度算法每次从就绪队列中选择优先级最高的进程,将CPU分配给它,使之投入运行。 ↩

^{短作业优先(JSF)调度算法}. 短作业(进程)优先调度算法是指对短作业(进程)优先调度的算法。短作业优先(SJF)调度算法从后备队列中选择一个或几个估计运行时间最短的作业,将它们调入内存运行;短进程优先(SPF)调度算法从就绪队列中选择一个估计运行时间最短的进程,将CPU分配给它,使之立即执行,直到完成或发生某事件而阻塞时才释放CPU。 ↩

^{先来先服务(FCFS)调度算法}. FCFS调度算法是一种最简单的调度算法,它既可用于作业调度,又可用于进程调度。 ↩

^{上下文切换与模式切换}. 模式切换与上下文切换是不同的,模式切换时,CPU逻辑上可能还在执行同一进程。用户进程最开始都运行在用户态,若进程因中断或异常进入核心态运行,执行完后又回到用户态刚被中断的进程运行。用户态和内核态之间的切换称为模式切换,而不是上下文切换,因为没有改变当前的进程。上下文切换只能发生在内核态,它是多任务操作系统中的一个必需的特性。 ↩

^{上下文切换的消耗}. 上下文切换通常是计算密集型的,即它需要相当可观的CPU时间,在每秒几十上百次的切换中,每次切换都需要纳秒量级的时间,所以上下文切换对系统来说意味着消耗大量的CPU时间。有些CPU提供多个寄存器组,这样,上下文切换就只需要简单改变当前寄存器组的指针。 ↩

^{上下文切换}. 切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态,这个任务称为上下文切换。进程上下文采用进程PCB表示,包括CPU寄存器的值、进程状态和内存管理信息等。当进行上下文切换时,内核将旧进程状态保存在其PCB中,然后加载经调度而要执行的新进程的上下文。在切换过程中,进程的运行环境产生实质性的变化。上下文切换的流程如下： ↩

^响应时间. 指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中,周转时间不是最好的评价准则,一般采用响应时间作为衡量调度算法的重要准则之一。从用户角度来看,调度策略应尽量降低响应时间,使响应时间处在用户能接受的范围之内。 ↩

^等待时间. 指进程处于等待CPU的时间之和,等待时间越长,用户满意度越低。CPU调度算法实际上并不影响作业执行或I/O操作的时间,只影响作业在就绪队列中等待所花的时间。因此,衡量一个调度算法的优劣,常常只需简单地考察等待时间。 ↩

^周转时间. 指从作业提交到作业完成所经历的时间,是作业等待、在就绪队列中排队、在CPU上运行及/O操作所花费时间的总和。 ↩

^{系统吞吐量}. 表示单位时间内CPU完成作业的数量。长作业需要消耗较长的CPU时间,因此会降低系统的吞吐量。而对于短作业,需要消耗的CPU时间较短,因此能提高系统的吞吐量。调度算法和方式的不同,也会对系统的吞吐量产生较大的影响。 ↩

^CPU利用率. CPU是计算机系统中最重要和昂贵的资源之一,所以应尽可能使CPU保持“忙”状态,使这一资源利用率最高。 ↩

^{内核级线程调度}. 内核选择一个特定线程运行,通常不用考虑该线程属于哪个进程。对被选择的线程赋予一个时间片,如果超过了时间片,就会强制挂起该线程。 ↩

^{用户级线程调度}. 由于内核并不知道线程的存在,所以内核还是和以前一样,选择一个进程,并给予时间控制。由进程中的调度程序决定哪个线程运行。 ↩

^闲逛进程. 在进程切换时,如果系统中没有就绪进程,就会调度闲逛进程(Idle Process)运行,它的PID为0。如果没有其他进程就绪,该进程就一直运行,并在指令周期后测试中断。闲逛进程的优先级最低,没有就绪进程时才会运行闲逛进程,只要有进程就绪,就会立即让出CPU。
闲逛进程不需要CPU之外的资源,它不会被阻塞。 ↩

^{上下文切换器}. 在对CPU进行切换时,会发生两对上下文的切换操作：第一对,将当前进程的上下文保存到其PCB中,再装入分派程序的上下文,以便分派程序运行;第二对,移出分派程序的上下文,将新选进程的CPU现场信息装入CPU的各个相应寄存器。 ↩

^分派器. 依据调度程序所选的进程,将其从就绪队列中取出,将CPU分配给新进程。 ↩

^排队器. 将系统中的所有就绪进程按照一定的策略排成一个或多个队列,以便于调度程序选择。每当有一个进程转变为就绪态时,排队器便将它插入相应的就绪队列。 ↩

^{低级调度(进程调度)}. 按照某种算法从就绪队列中选取一个进程,将CPU分配给它。进程调度是最基本的一种调度,在各种操作系统中都必须配置这级调度。进程调度的频率很高,一般几十毫秒一次。 ↩

^{中级调度(内存调度)}. 引入中级调度的目的是提高内存利用率和系统吞吐量。为此,将那些暂时不能运行的进程调至外存等待,此时进程的状态称为挂起态。当它们已具备运行条件且内存又稍有空闲时,由中级调度来决定将外存上的那些已具备运行条件的挂起进程再重新调入内存,并修改其状态为就绪态,挂在就绪队列上等待。中级调度实际上是存储器管理中的对换功能。 ↩

^{高级调度(作业调度)}. 按照某种规则从外存上处于后备队列的作业中挑选一个(或多个),给它(们)分配内存、I/O设备等必要的资源,并建立相应的进程,以使它(们)获得竞争CPU的权利。简言之,作业调度就是内存与辅存之间的调度。每个作业只调入一次、调出一次。多道批处理系统中大多配有作业调度,而其他系统中通常不需要配置作业调度. ↩

^{调度的基本概念}. 在多道程序系统中,进程的数量往往多于CPU的个数,因此进程争用CPU的情况在所难免。CPU调度是对CPU进行分配,即从就绪队列中按照一定的算法(公平、高效的原则)选择一个进程并将CPU分配给它运行,以实现进程并发地执行。CPU调度是多道程序操作系统的基础,是操作系统设计的核心问题。 ↩

^{线程的基本概念}. 引入进程的目的是更好地使多道程序并发执行,提高资源利用率和系统吞吐量：而引入线程(Threads)的目的则是减小程序在并发执行时所付出的时空开销,提高操作系统的并发性能。
线程最直接的理解就是轻量级进程,它是一个基本的CPU执行单元,也是程序执行流的最小单元,由线程D、程序计数器、寄存器集合和堆栈组成。线程是进程中的一个实体,是被系统独立调度和分派的基本单位,线程自己不拥有系统资源,只拥有一点儿在运行中必不可少的资源,但它可与同属一个进程的其他线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程,同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约,致使线程在运行中呈现出间断性。线程也有就绪、阻塞和运行三种基本状态。
引入线程后,进程的内涵发生了改变,进程只作为除CPU外的系统资源的分配单元,而线程则作为CPU的分配单元。由于一个进程内部有多个线程,若线程的切换发生在同一个进程内部,则只需要很少的时空开销。下面从几个方面对线程和进程进行比较。 ↩

^{注意Block&Wakeup}. Block原语和Wakeup原语是一对作用刚好相反的原语,必须成对使用。如果在某进程中调用了Block原语,则必须在与之合作的或其他相关的进程中安排一条相应的Wakeup原语,以便唤醒阻塞进程：否则,阻塞进程将会因不能被唤醒而永久地处于阻塞状态。 ↩

^{进程的阻塞和唤醒}. 正在执行的进程,由于期待的某些事件未发生,如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新任务可做等,进程便通过调用阻塞原语(Blo©k),使自己由运行态变为阻塞态。可见,阻塞是进程自身的一种主动行为,也因此只有处于运行态的进程(获得CPU),才可能将其转为阻塞态 ↩

^{进程的终止}. 引起进程终止的事件主要有：①正常结束,表示进程的任务己完成并准备退出运行。②异常结束,表示进程在运行时,发生了某种异常事件,使程序无法继续运行,如存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、I/O故障等。③外界干预,指进程应外界的请求而终止运行,如操作员或操作系统干预、父进程请求和父进程终止。 ↩

^{进程的创建}. 允许一个进程创建另一个进程,此时创建者称为父进程,被创建的进程称为子进程。子进程可以继承父进程所拥有的资源。当子进程被撤销时,应將其从父进程那里获得的资源归还给父进程。此外,在撤销父进程时,通常也会同时撤销其所有的子进程。
在操作系统中,终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都会引起进程的创建。 ↩

^索引方式. 索引方式将同一状态的进程组织在一个索引表中,索引表的表项指向相应的PCB,不同状态对应不同的索引表,如就绪索引表和阻塞索引表等。 ↩

^链接方式. 链接方式将同一状态的PCB链接成一个队列,不同状态对应不同的队列,也可把处于阻塞态的进程的PCB,根据其阻塞原因的不同,排成多个阻塞队列。 ↩

^数据段. 一个进程的数据段,可以是进程对应的程序加工处理的原始数据,也可以是程序执行时产生的中间或最终结果。 ↩

^程序段. 程序段就是能被进程调度程序调度到CPU执行的程序代码段。注意,程序可被多个进程共享,即多个进程可以运行同一个程序。 ↩

^终止态. 进程正从系统中消失,可能是进程正常结束或其他原因退出运行。进程需要结束运行时,系统首先将该进程置为终止态,然后进一步处理资源释放和回收等工作。 ↩

^创建态. 进程正在被创建,尚未转到就绪态。创建进程需要多个步骤：首先申请一个空白的PCB,并向PCB中填写用于控制和管理进程的信息;然后为该进程分配运行时所必须的资源;最后把该进程转入就绪态并插入就绪队列。但是,如果进程所需的资源尚不能得到满足,如内存不足,则创建工作尚未完成,进程此时所处的状态称为创建态 ↩

^阻塞态. 又称等待态。进程正在等待某一事件而暂停运行,如等待某资源为可用(不包括处理机)或等待输入/输出完成。即使处理机空闲,该进程也不能运行。系统通常将处于阻塞态的进程也排成一个队列,甚至根据阻塞原因的不同,设置多个阻塞队列。 ↩

^就绪态. 进程获得了除处理机外的一切所需资源,;一旦得到处理机,便可立即运行。系统中处于就绪状态的进程可能有多个,通常将它们排成一个队列,称为就绪队列。 ↩

^运行态. 进程正在处理机上运行。在单处理机中,每个时刻只有一个进程处于运行态。 ↩

^异步性. 由于进程的相互制约,使得进程按各自独立的、不可预知的速度向前推进。异步性会导致执行结果的不可再现性。 ↩

^独立性. 指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序,都不能作为一个独立的单位参与运行。 ↩

^并发性. 指多个进程实体同存于内存中,能在一段时间内同时运行。引入进程的目的就是使进程能和其他进程并发执行。并发性是进程的重要特征,也是操作系统的重要特征。 ↩

^动态性. 进程是程序的一次执行,他有着创建、活动、暂停、终止等过程,具有一定的生命周期,是动态地产生、变化和消亡的。动态性是进程最基本的特征。 ↩